package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * <a href="https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solutions/">从上到下打印二叉树 III</a>
 * 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
 * <pre>
 *          8
 *         /  \
 *        6    10
 *            /  \
 *           2    1
 *  输入：{8,6,10,#,#,2,1}
 *  返回值：
 *      [
 *          [8],
 *          [10,6],
 *          [2,1]
 *      ]
 * </pre>
 *
 * @author c2b
 * @since 2023/3/9 13:44
 */
public class JzOffer0032LevelOrder_III {

    /**
     * <p>队双栈</p>
     * step 1：首先判断二叉树是否为空，空树没有遍历结果。<br>
     * step 2：建立双栈，首先将根节点压入stack1。<br>
     * step 3：每次遍历一个栈，根据标志位将子节点压入栈。<br>
     * step 4：遍历完成，改变标志位，直到两个栈都为空。<br>
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);
        // 是否从左往右打印,true：从左往右打印 false:从右往左打印
        boolean isOrderFromLeftToRight = true;
        List<Integer> tempList = new ArrayList<>();
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            TreeNode currNode;
            if (isOrderFromLeftToRight) {
                // 说明正在处理stack1中的节点
                while (!stack1.isEmpty()) {
                    currNode = stack1.pop();
                    tempList.add(currNode.val);
                    // 按照先左后后的顺序将子节点压入stack2
                    if (currNode.left != null) {
                        stack2.push(currNode.left);
                    }
                    if (currNode.right != null) {
                        stack2.push(currNode.right);
                    }

                }
            } else {
                // 说明正在处理stack2中的节点
                while (!stack2.isEmpty()) {
                    currNode = stack2.pop();
                    tempList.add(currNode.val);
                    // 按照先右后左的顺序将子节点压入stack1
                    if (currNode.right != null) {
                        stack1.push(currNode.right);
                    }
                    if (currNode.left != null) {
                        stack1.push(currNode.left);
                    }
                }
            }
            res.add(tempList);
            tempList = new ArrayList<>();
            isOrderFromLeftToRight = !isOrderFromLeftToRight;
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(6);
        root.right = new TreeNode(10);
        root.right.left = new TreeNode(2);
        root.right.right = new TreeNode(1);
        JzOffer0032LevelOrder_III jzOffer0032PrintFromTopToBottom = new JzOffer0032LevelOrder_III();
        List<List<Integer>> lists = jzOffer0032PrintFromTopToBottom.levelOrder(root);
        for (List<Integer> list : lists) {
            for (Integer integer : list) {
                System.out.print(integer + "  ");
            }
            System.out.println();
        }
    }
}
